1. Field
Apparatuses and methods consistent with exemplary embodiments relate to encoding and decoding of parity check codes, and more particularly, to encoding and decoding of parity check codes capable of performing low density parity check (LDPC) encoding and decoding based on a parity check matrix.
2. Description of the Related Art
In a communication/broadcasting system, link performance may be significantly deteriorated due to several types of noise in a channel, a fading phenomenon, and inter-symbol interference (ISI). Therefore, in order to implement high speed digital communication/broadcasting systems requiring a high data throughput and reliability, such as the next generation mobile communication, digital broadcasting and portable Internet, it has been required to develop a technology to address problems occurring from the noise, fading, ISI, etc. Studies on an error correcting code has been recently conducted actively as a method for increasing reliability of communication by efficiently reconstructing distorted information.
In the 1960s, an LDPC code initially introduced by Gallager has been forgotten for a long time due to technological complexity of the LDPC code that could not be implemented by a technology level in those days. However, as a turbo code suggested by Berrou, Glavieux, and Thitimajshima in 1993 shows performance approaching a channel capacity of Shannon, many analyses for performance and features of the turbo code have been conducted. Therefore, many studies on channel encoding based on a graph and iterative decoding have been conducted. As a result, the LDPC code was again studied in the latter half of the 1990s, such that is has been revealed that the performance approaches the channel capacity of the Shannon when decoding is performed by applying iterative decoding based on a sum-product algorithm on a Tanner graph corresponding to the LDPC code.
The LDPC code is generally defined as a parity check matrix and may be represented by a bipartite graph commonly called a Tanner graph.
Hereinafter, a systematic LDPC codeword will be described with reference to FIG. 1. The LDPC codes are LDPC encoded by receiving an information word 102 formed of Kldpc bits or symbols to generate a codeword 100 formed of Nldpc bits or symbols. Hereinafter, for convenience of explanation, it is assumed that the codeword 100 formed of Nldpc bits is generated by receiving the information word 102 including Kldpc bits. That is, when the information word I=[i0, i1, i2, . . . , iKldpc−1] 102 which is formed of Kldpc input bits is LDPC encoded, the codeword c=[c0, c1, c2, c3, . . . , cNldpc−1] 100 is generated. That is, the codeword is a bit string formed of a plurality of bits and the bits of the codeword represent each bit forming the codeword. Further, the information word is a bit string formed of a plurality of bits and the bits of the information word represent each bit forming the information word. In this case, in the case of a systematic code, the codeword is formed of C=[c0, c1, c2, . . . , cNldpc−1]=[i0, i1, i2, . . . , iKldpc−1, p0, p1, p2, . . . , pNldpc−Kldpc−1]. Here, P=[p0, p1, p2, . . . , pNldpc−Kldpc−1] is a parity 104 and the number Nparity of parity bits is as follows. Nparity=Nldpc−Kldpc.
The LDPC codes are a kind of linear block codes and include a process of determining a codeword satisfying conditions of following mathematical expression 1.
                                                        H              ·                              c                T                                      =                                                            [                                                            h                      0                                        ⁢                                          h                      1                                        ⁢                                          h                      2                                        ⁢                                                                                  ⁢                    …                    ⁢                                                                                  ⁢                                          h                                                                        N                          ldpc                                                -                        1                                                                              ]                                ·                                  c                  T                                            =                                                                    ∑                                          i                      =                      0                                                                                      N                        ldpc                                            -                      1                                                        ⁢                                                            c                      i                                        ·                                          h                      i                                                                      =                0                                              ,                                          ⁢          where                ⁢                                  ⁢                  c          =                                    [                                                c                  0                                ,                                  c                  1                                ,                                  c                  2                                ,                …                ⁢                                                                  ,                                  c                                                            N                      ldpc                                        -                    1                                                              ]                        .                                              (        1        )            
In mathematical expression 1 above, H represents the parity-check matrix, C represents the codeword, ci represents an i-th bit of the codeword, and Nldpc represents a codeword length. Here, hi represents an i-th column of the parity-check matrix H.
The parity-check matrix H is formed of the same Nldpc columns as the number of bits of the LDPC codeword. The mathematical expression 1 represents that since a sum of a product of the i-th column hi of the parity-check matrix and the i-th bit ci of the codeword becomes “0”, the i-th column hi has a relationship with the i-th bit ci of the codeword.
Meanwhile, the performance of the LDPC codes may be determined according to the parity-check matrix. Therefore, there is a need to design the parity-check matrix for the LDPC codes having improved performance.